package pl.mmadej.ds4java.ds.list;

import pl.mmadej.ds4java.ds.array.ArrayDecorator;
import pl.mmadej.ds4java.ds.common.BaseIterator;

import java.util.Comparator;
import java.util.Iterator;

public class LinkedList<T> extends AbstractList<T> implements List<T> {

    private LinkedListNode rootGuard;
    private LinkedListNode tailGuard;

    @SuppressWarnings("unchecked")
    public LinkedList() {
        rootGuard = new LinkedListNode("ROOT");
        tailGuard = new LinkedListNode("TAIL");
        tailGuard.setNext(rootGuard);
        tailGuard.setPrevious(rootGuard);
        rootGuard.setPrevious(tailGuard);
        rootGuard.setNext(tailGuard);
    }

    @Override
    public boolean contains(T element) {
        return indexOf(element) != -1;
    }

    @Override
    @SuppressWarnings("unchecked")
    public int indexOf(T element) {
        int index = 0;
        LinkedListNode<T> node = rootGuard.getNext();
        while (node != tailGuard) {
            if (node.getValue().equals(element)) {
                return index;
            }
            index++;
            node = node.getNext();
        }
        return -1;
    }

    @Override
    @SuppressWarnings("unchecked")
    public void insert(T element) {
        addBefore(tailGuard, element);
    }

    @Override
    @SuppressWarnings("unchecked")
    public void insertAt(int index, T element) {
        assertIndexInBounds(index, 0, size());
        LinkedListNode node = tailGuard;
        if (index != size()) {
            node = nodeAt(index);
        }
        addBefore(node, element);
    }

    @Override
    public T searchAt(int index) {
        return nodeAt(index).getValue();
    }

    @Override
    public T deleteAt(int index) {
        return delete(nodeAt(index));
    }

    @Override
    @SuppressWarnings("unchecked")
    public boolean delete(T element) {
        LinkedListNode<T> node = rootGuard.getNext();
        while (node != tailGuard) {
            if (node.getValue().equals(element)) {
                delete(node);
                return true;
            }
            node = node.getNext();
        }
        return false;
    }

    @Override
    @SuppressWarnings("unchecked")
    public T deleteLast() {
        if (empty()) {
            return null;
        }
        return delete(tailGuard.getPrevious());

    }

    @Override
    @SuppressWarnings("unchecked")
    public T deleteFirst() {
        if (empty()) {
            return null;
        }
        return delete(rootGuard.getNext());

    }

    @Override
    @SuppressWarnings("unchecked")
    public T searchLast() {
        if (empty()) {
            return null;
        }
        return (T) tailGuard.getPrevious().getValue();
    }

    @Override
    @SuppressWarnings("unchecked")
    public T searchFirst() {
        if (empty()) {
            return null;
        }
        return (T) rootGuard.getNext().getValue();
    }

    @Override
    public Iterator<T> iterator() {
        return new LinkedListIterator();
    }

    @Override
    public List<T> toUnmodifiable() {
        return new UnmodifableList<T>(this);
    }

    @Override
    @SuppressWarnings("unchecked")
    public <E> E[] toArray(E[] resultArray) {
        resultArray = createArrayIfNeeded(resultArray, size());
        int i = 0;
        for (LinkedListNode<T> node = rootGuard.getNext(); node != tailGuard; node = node.getNext()) {
            resultArray[i++] = (E) node.getValue();
        }
        return resultArray;
    }

    @Override
    public void sort(Comparator<T> comparator) {
        int elementsCount = size();
        ArrayDecorator<T> array = toArrayObject();
        clear();
        array.quickSort(0, elementsCount - 1, comparator);
        for (int index = 0; index < elementsCount; index++) {
            insert(array.elementAt(index));
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void clear() {
        tailGuard.setNext(rootGuard);
        tailGuard.setPrevious(rootGuard);
        rootGuard.setNext(tailGuard);
        rootGuard.setPrevious(tailGuard);
        setSize(0);
    }

    @Override
    @SuppressWarnings("unchecked")
    public void reverse() {
        LinkedListNode<T> node = rootGuard.getNext();
        LinkedListNode<T> next = rootGuard.getNext();
        LinkedListNode<T> previous;
        rootGuard.setNext(tailGuard.getPrevious());
        tailGuard.setPrevious(next);

        while (node != tailGuard) {
            next = node.getNext();
            previous = node.getPrevious();
            node.setNext(previous == rootGuard ? tailGuard : previous);
            node.setPrevious(next == tailGuard ? rootGuard : next);
            node = next;
        }
    }

    private ArrayDecorator<T> toArrayObject() {
        ArrayDecorator<T> array = new ArrayDecorator<T>(size());
        Iterator<T> iterator = iterator();
        int index = 0;
        while (iterator.hasNext()) {
            array.setAt(index++, iterator.next());
        }
        return array;
    }

    private T delete(LinkedListNode<T> node) {
        node.getPrevious().setNext(node.getNext());
        node.getNext().setPrevious(node.getPrevious());
        T value = node.getValue();
        decrementSize();
        return value;
    }

    @SuppressWarnings("unchecked")
    private LinkedListNode<T> nodeAt(int index) {
        assertIndexInBounds(index, 0, size() - 1);
        int iterationIndex = 0;
        LinkedListNode<T> node = rootGuard.getNext();
        //index is in bounds
        while (index != iterationIndex++) {
            node = node.getNext();
        }
        return node;
    }

    private void addBefore(LinkedListNode<T> node, T element) {
        assertNotNull(element);
        LinkedListNode<T> newNode = new LinkedListNode<T>(element);
        LinkedListNode<T> previous = node.getPrevious();
        node.setPrevious(newNode);
        newNode.setNext(node);
        newNode.setPrevious(previous);
        previous.setNext(newNode);
        incrementSize();
    }

    private class LinkedListIterator extends BaseIterator<T> {

        private LinkedListNode node = rootGuard;

        @Override
        public boolean hasNext() {
            return node.getNext() != tailGuard;
        }

        @Override
        @SuppressWarnings("unchecked")
        public T doNext() {
            node = node.getNext();
            return (T) node.getValue();
        }

        @Override
        @SuppressWarnings("unchecked")
        public void doRemove() {
            delete(node);
        }

        protected boolean walkingNotStarted() {
            return node == rootGuard;
        }

        protected boolean walkingEnded() {
            return node.getNext() == tailGuard;
        }
    }
}
